Game mở đầu với cảnh nhân vật chính Tommy Angelo đang đi vào quán bar để nói chuyện với tay thám tử người Ireland Norman. Tommy đề nghị thám tử Norman bảo vệ gia đình anh để Tommy khai toàn bộ sự thật tội ác về gia đình Salieri. Từ đó câu chuyện dẫn dắt người chơi từ hiện tại về quá khứ, một trong những điểm được đánh giá cao trong Mafia.

Khi còn làm tài xế taxi tại thành phố Lost Heaven vào những năm 1930, Tommy bất ngờ gặp phải hai người bạn đồng hành mới là Paulie và Sam và từ đây anh đã dấn thân vào con đường tội lỗi (người chơi sẽ gặp phải trong nhiệm vụ "An Offer You Cannot Refuse").Tommy sẽ gặp Don Salieri và trở thành một thành viên của băng này để chống lại Don Morello (đứng đầu băng Morello-đối địch với băng Salieri).Vụ việc tham gia băng này được dẫn từ một vụ việc khi Tommy bị hai đàn em băng Morello đánh đập và đòi giết, khi chạy đến quán bar Don Salieri, Tom nhận được sự giúp đỡ của Paulie-Sam-băng Salieri.

Trong vòng 8 năm hoạt động cho băng nhóm, Tom đã tham gia nhiều vụ việc như ám sát các gangster, ăn cắp tài sản, bắn chết ứng cử viên thị trưởng, tham gia các cuộc đua xe ăn tiền, cướp nhà băng và phá huỷ các cơ sở hạ tầng.Qua nhiều nhiệm vụ, kinh nghiệm làm việc và xử lý công việc của Tommy càng dày dặn hơn.Mặc dù là một mafia tàn nhẫn nhưng đâu đó trong tâm hồn Tommy vẫn còn sự nhân hậu và trái tim của con người, được thể hiện qua một số hành động như thả cho Frank(thay vì phải giết ông ta) bay qua thành phố khác nhằm trốn tránh sự truy sát của nhà Salieri, không ra tay bắn chết gái điếm Michelle (là một khách hàng của nhà Salieri nhưng đã biết được một số thông tin mật). Đối với các đối thủ gangster khác, Tommy tỏ ra là một đàn em lạnh lùng, anh chuyên thực hiện một số nhiệm vụ ám sát đầu lõi băng Morello. Sau 3 lần ám sát hụt (người chơi sẽ gặp trong nhiệm vụ "You Lucky Bastard"), cuối cùng em trai của Don Morello là Sergio Morello bị Tommy bắn chết tại bến cảng.Ngay sau đó, Paulie-Sam-Tommy tìm đến giết chết Don tại sân bay(hoặc húc rớt xuống vực thẳm-vì game chia nhiệm vụ này thành hai đường, nếu người chơi rượt nhanh, Don sẽ đi vào xuống cầu[8], nếu người chơi rượt chậm, Don sẽ đi vào sân bay[9]).

Sau khi thanh toán xong băng Morello, nội bộ gia đình Salieri xảy ra chuyện lục đục, Paulie(đã trở thành bạn thân của Tommy) đã phát hiện Don Salieri ăn cắp hết số kim cương và đòi không chia lợi nhuận cho các đàn em của mình(mà Tom lấy cắp được trong nhiệm vụ "Just For Relaxtion").Sáng hôm sau, Pau mời Tom đến nhà và rủ đi ăn cướp nhà băng(người chơi sẽ gặp trong nhiệm vụ "Moonlighting");sau một hồi suy nghĩ Tommy đồng ý và đi theo Paulie.Cốt truyện li kì và bất ngờ khiến cho người chơi được dẫn hết từ tình tiết này đến tình tiết khác.Sau khi ăn cướp nhà băng và đào tẩu thành công, Paulie và Tom đã bị Sam lừa và sáng hôm sau khi Tom đến căn hộ của Pau định chia tiền thì thấy Paulie đã bị giết với hơn chục vết đạn trên người(anh ta bị giết bằng súng thục).Tom được Sam gọi thông báo là Salieri đã biết hết mọi chuyện và sẽ cử người hoặc cảnh sát đến căn hộ đó ngay lập tức(nhưng thật ra Sam mới chính là người đã khai báo toàn bộ).Trong màn cuối cùng(nhiệm vụ "The Death Of Art"), Tom sẽ thay mặt Paulie giết chết tên phản bội Sam và kết liễu Sam bằng nhiều phát đạn Colt[10].

Sau khi thanh toán xong toàn bộ băng đảng Salieri cũng như Morello, Tommy nhanh chóng bay sang Châu Âu cùng với Sarah(con gái người phục vụ quán bar Luigi, sau này trở thành vợ Tommy).Anh sắp xếp một cuộc gặp mặt với thám tử Norman để phơi bày toàn bộ sự thật về cái xã hội đen mà anh đã từng tham gia.Cuối cùng, hơn 80 gangster cùng Don Salieri dành toàn bộ cuộc đời để "bóc lịch".Tommy và gia đình được liên bang bảo vệ trong suốt hơn 13 năm và di chuyển về miền quê để sống nốt quãng đời còn lại.

Nhưng cuối cùng, Tommy vẫn bị hai gangster là Joe Barbaro - Vito Scalleta (hai gangster thuộc gia đình Falcone) giết chết ngay tại nhà.Anh than thở và kể lại rằng toàn bộ cuộc đời anh chỉ là một chuỗi sai lầm, cuối cùng anh vẫn phải gánh chịu cái sai lầm đó.

• Sau đây là đoạn trích về lời than thở của Tommy:

• Tạm dịch: